Johnson bound

In applied mathematics, the Johnson bound (named after Selmer Martin Johnson) is a limit on the size of error-correcting codes, as used in coding theory for data transmission or communications.

---

Definition Let $C$ be a q-ary code of length $n$, i.e. a subset of $\backslash mathbb\{F\}\_q^n$. Let $d$ be the minimum distance of $C$, i.e.

$d\; =\; \backslash min\_\{x,y\; \backslash in\; C,\; x\; \backslash neq\; y\}\; d(x,y),$

where $d(x,y)$ is the Hamming distance between $x$ and $y$.

Let $C\_q(n,d)$ be the set of all q-ary codes with length $n$ and minimum distance $d$ and let $C\_q(n,d,w)$ denote the set of codes in $C\_q(n,d)$ such that every element has exactly $w$ nonzero entries.

Denote by $|C|$ the number of elements in $C$. Then, we define $A\_q(n,d)$ to be the largest size of a code with length $n$ and minimum distance $d$:

$A\_q(n,d)\; =\; \backslash max\_\{C\; \backslash in\; C\_q(n,d)\}\; |C|.$

Similarly, we define $A\_q(n,d,w)$ to be the largest size of a code in $C\_q(n,d,w)$:

$A\_q(n,d,w)\; =\; \backslash max\_\{C\; \backslash in\; C\_q(n,d,w)\}\; |C|.$

Theorem 1 (Johnson bound for $A\_q(n,d)$):

If $d=2t+1$,

$A\_q(n,d)\; \backslash leq\; \backslash frac\{q^n\}\{\backslash sum\_\{i=0\}^t\; \{n\; \backslash choose\; i\}\; (q-1)^i\; +\; \backslash frac$

Post Comment